package com.seven.leetcode.problems;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * MinimumIndexSumOfTwoLists
 * https://leetcode-cn.com/problems/minimum-index-sum-of-two-lists/
 * 级别：Easy
 * <p>
 * 599. 两个列表的最小索引总和
 * 假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
 * <p>
 * 你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设答案总是存在。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["Piatti", "The Grill at Torrey Pines",
 * "Hungry Hunter Steakhouse", "Shogun"]
 * 输出: ["Shogun"]
 * 解释: 他们唯一共同喜爱的餐厅是“Shogun”。
 * 示例 2:
 * <p>
 * 输入:list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["KFC", "Shogun", "Burger King"]
 * 输出: ["Shogun"]
 * 解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。
 * <p>
 * <p>
 * 提示:
 * <p>
 * 1 <= list1.length, list2.length <= 1000
 * 1 <= list1[i].length, list2[i].length <= 30
 * list1[i] 和 list2[i] 由空格 ' ' 和英文字母组成。
 * list1 的所有字符串都是 唯一 的。
 * list2 中的所有字符串都是 唯一 的。
 *
 * @author Carl
 * @date 2022/03/14 21:59
 */
public class MinimumIndexSumOfTwoLists {

    public static void main(String[] args) {
        String[] list1 = {"Shogun", "Tapioca Express", "Burger King", "KFC"};
        String[] list2 = {"Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"};

        System.out.println("in:\nlist1: " + Arrays.toString(list1) + "\nlist2: " + Arrays.toString(list2));
        String[] res = minimumIndexSumOfTwoLists2(list1, list2);
        System.out.println("out: " + Arrays.toString(res));
    }

    public static String[] minimumIndexSumOfTwoLists(String[] list1, String[] list2) {
        List<String> y = Arrays.asList(list2);
        List<String> res = new LinkedList<>();
        int idx = Integer.MAX_VALUE;
        for (int j = 0; j < list1.length; j++) {
            String s = list1[j];
            int i = y.indexOf(s);
            if (i != -1) {
                if (idx > i + j) {
                    idx = i + j;
                    res.clear();
                    res.add(s);
                } else if (idx == i + j) {
                    res.add(s);
                }
            }
        }
        return res.toArray(new String[]{});
    }

    public static String[] minimumIndexSumOfTwoLists2(String[] list1, String[] list2) {
        return IntStream.range(0, list1.length + list2.length)
            .boxed()
            .collect(Collectors.groupingBy(i -> i < list1.length ? list1[i] : list2[i - list1.length]))
            .entrySet()
            .stream()
            .filter(entry -> entry.getValue().size() == 2)
            .collect(Collectors.groupingBy(entry -> entry.getValue().get(0) + entry.getValue().get(1), TreeMap::new,
                Collectors.mapping(Map.Entry::getKey, Collectors.toList())))
            .values()
            .iterator()
            .next()
            .toArray(new String[0]);
    }
}
